package 牛客;

import java.util.ArrayList;
import java.util.Arrays;

public class 最小路径和 {
    int[][] memo;
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        memo=new int[m][n];
      for (int[] row:memo){
          Arrays.fill(row,-1);
      }
      return dp(m-1,n-1,grid);
    }
    int dp(int a,int b,int[][] grid){
       if(a==0&&b==0) return grid[0][0];
       if(a<0||b<0) return Integer.MAX_VALUE;
       if(memo[a][b]!=-1){
           return memo[a][b];
       }
       memo[a][b]=Math.min(dp(a-1,b,grid),dp(a,b-1,grid))+grid[a][b];
       return memo[a][b];
    }


}
